package set;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class Permutation46 {

    public static class PermutationWrong {
        // redo at 2022.03.06
        public List<List<Integer>> permute(int[] nums) {
            // ERROR: 数量不是2^n, 而是n!
            List<List<Integer>> results = new ArrayList<>(1 << (nums.length-1));
            // ERROR: 最外层不是一个循环, 而是仅仅从0开始.
            for (int i = 0; i < nums.length; i++) {
                swapRecursively(nums, i, results);
            }
            return results;
        }

        public void swapRecursively(int[] nums, int index, List<List<Integer>> results) {
            if (index == nums.length-1) {
                List<Integer> result = new ArrayList<>(nums.length);
                for (int n: nums) {
                    result.add(n);
                }
                results.add(result);
            } else {
                // ERROR: 不应该有双重循环, 只应该有一重, 并且要从index开始, 自己跟自己交换.
                for (int i = index; i < nums.length; i++) {
                    for (int j = i+1; j < nums.length; j++) {
                        swap(nums, i, j);
                        // ERROR: 子递归不应该从i+1开始, 应该从index+1
                        swapRecursively(nums, i+1, results);
                        swap(nums, i, j);
                    }
                }
            }
        }

        public void swap(int[] nums, int i, int j) {
            int t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
    }

    @Test
    public void test() {
        permute(new int[]{1});
        permute(new int[]{1, 2, 3, 4});
    }

    public List<List<Integer>> permute(int[] n) {
        int count = 1;
        for (int i = 1; i <= n.length; i++) {
            count *= i;
        }
        List<List<Integer>> results = new ArrayList<>(count);
        permuteRecursively(n, 0, results);
        System.out.println(results.size());
        for (List<Integer> r: results) {
            System.out.println(r);
        }
        System.out.println();
        return results;
    }

    public void permuteRecursively(int[] n, int k, List<List<Integer>> results) {
        if (k == n.length-1) {
            results.add(buildResult(n));
            return;
        }

        for (int i = k; i < n.length; i++) {
            swap(n, k, i);
            permuteRecursively(n, k+1, results);
            swap(n, k, i);
        }
    }

    public List<Integer> buildResult(int[] n) {
        List<Integer> list = new ArrayList<>(n.length);
        for (int i: n) {
            list.add(i);
        }
        return list;
    }

    public void swap(int[] n, int i, int j) {
        int t = n[i];
        n[i] = n[j];
        n[j] = t;
    }
}
